package com.cango.student.algorithm.sort;


/**
 * 插入排序
 * <p>
 * 时间复杂度（平均）	时间复杂度（最坏)	时间复杂度（最好)	空间复杂度	稳定性	复杂性
 * O(n2) 	                O(n2)	          O(n)	    O(1)	稳定	     简单
 */
public class InsertSort {
    public static void main(String[] args) {
//        Integer[] arr = {34,8,64,51,32,21};
        Integer[] arr = {64, 51, 34, 32, 21, 8};
//        insertSort(arr);
//        Integer[] arr = {8,34,64,51,32,21};
//        Integer[] arr = {8,34,64,51,32,21};
//        Integer[] arr = {8,34,51,64,32,21};
        //        Integer[] arr = {8,32,34,51,64,21};
        //        Integer[] arr = {8,21,32,34,51,64};

//        for (int i = 1; i < arr.length; i++) {
//            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
//                int tmp = arr[j - 1];
//                arr[j - 1] = arr[j];
//                arr[j] = tmp;
//            }
//        }
        // i代表起始位置,第1个开始
        for (int i = 1; i < arr.length; i++) {
            // 保存当前位置i的元素，其中[0,i-1]已经有序
            Integer tmp = arr[i];

            int j;
            // 目的是让[0,i]成为有序
            // 当tmp > arr[j-1]时，因为有序序列，j--就不再执行，j是合适的位置，
            for (j = i; j > 0 && tmp < arr[j - 1]; j--) {
                arr[j] = arr[j - 1];//后移一位
            }
            arr[j] = tmp;//插入到合适的位置
        }



        for (Integer i : arr) {
            System.out.print(i + " ");
        }
    }
}
